package GraphType.Movement_of_arr;


import java.util.*;

public class SolutionBFS {
    static int[] visit;
    static int n;
    static Deque<Node> queue = new ArrayDeque<Node>();
    static class Node{
        int step;
        int x;
        public Node(int x,int step){
            this.x=x;
            this.step=step;
        }

    }
    public static void main(String[] args) {
        n = 100;
        visit = new int[n*2];
        int x = 20, end = 81;
        bfs(x,end);

    }

    private static void bfs(int x, int end) {
        queue.add(new Node(x,0));
        while (!queue.isEmpty()){
            Node first = queue.getFirst();
            if (first.x==end){
                System.out.println(first.step);
                break;
            }

            if (first.x + 1<=n && visit[first.x + 1] == 0) {
                queue.add(new Node(first.x+1,first.step+1));
                visit[first.x+1]=1;
            }
            if (first.x - 1>=0 && visit[first.x-1]==0){
                queue.add(new Node(first.x-1,first.step+1));
                visit[first.x-1]=1;
            }
            if (first.x*2 <=n &&visit[first.x*2]==0){
                queue.add(new Node(first.x*2,first.step+1));
                visit[first.x*2]=1;
            }
            queue.poll();
        }
    }
}
